//某班级学号记录系统发生错乱，原整数学号序列 [1,2,3,4,...] 分隔符丢失后变为 1234... 的字符序列。请实现一个函数返回该字符序列中的第 
//k 位数字。 
//
// 
//
// 示例 1： 
//
// 
//输入：k = 5
//输出：5
// 
//
// 示例 2： 
//
// 
//输入：k = 12
//输出：1
//解释：第 12 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 1 ，它是 11 的一部分。 
//
// 
//
// 提示： 
//
// 
// 0 <= k < 2³¹ 
// 
//
// 注意：本题与主站 400 题相同：https://leetcode-cn.com/problems/nth-digit/ 
//
// 
//
// Related Topics 数学 二分查找 👍 370 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-05-14 22:58:56
 * @description LCR 163.找到第 k 位数字
 */
public class ShuZiXuLieZhongMouYiWeiDeShuZiLcof{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ShuZiXuLieZhongMouYiWeiDeShuZiLcof fun=new ShuZiXuLieZhongMouYiWeiDeShuZiLcof();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public int findKthNumber(int k) {
		int digit = 1, cnt = 9, baseNum = 1;
		while((long)digit * cnt < k){
			k -= digit * cnt;
			digit++;
			cnt *= 10;
			baseNum *= 10;
		}
		int num = baseNum + (k - 1) / digit;
		int idx = (k - 1) % digit;
		return String.valueOf(num).charAt(idx) - '0';
    }
	public int findKthNumber1(int n) {
		int d = 1, count = 9;
		while (n > (long) d * count) {
			n -= d * count;
			d++;
			count *= 10;
		}
		int index = n - 1;
		int start = (int) Math.pow(10, d - 1);
		int num = start + index / d;
		int digitIndex = index % d;
		int digit = (num / (int)(Math.pow(10, d - digitIndex - 1))) % 10;
		return digit;
	}
	//需要知道第k位数字在第几个数的第几位
	//1-9 1位数 10-99 2位数 100-999 3位数
	//1-9 和是9,10-99 和是180,100-999 和是2700
	//x 位数的和是9*10^(x-1)*x
	//因为n最大是2^31-1,所以最多9位数
	//
	public int findKthNumber2(int n) {
		int low = 1, high = 9;
		//二分查找，先找到第k位数字在第几个数上
		while (low < high) {
			int mid = (high - low) / 2 + low;
			if (totalDigits(mid) < n) {
				low = mid + 1;
			} else {
				high = mid;
			}
		}
		//low就是应该是几位数
		int d = low;
		//low-1已经有多少位数了
		int prevDigits = totalDigits(d - 1);
		//low-1的位数加上差值就是这个数的第几位
		int index = n - prevDigits - 1;
		//计算这个数
		int start = (int) Math.pow(10, d - 1);
		int num = start + index / d;
		int digitIndex = index % d;
		int digit = (num / (int) (Math.pow(10, d - digitIndex - 1))) % 10;
		return digit;
	}

	public int totalDigits(int length) {
		int digits = 0;
		int curLength = 1, curCount = 9;
		while (curLength <= length) {
			digits += curLength * curCount;
			curLength++;
			curCount *= 10;
		}
		return digits;
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
